#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define swap(a,b) {typeof(a) t=a; a=b; b=t;}	//定义一个swap用于交换，便于使用

/*堆排序：
		首先把数据构当作完全二叉树，然后保证根点最大，然后把根结点与最后一个元素交换，
	然后再调整二叉树（逐渐减少数组），让根依然保持最大，重复上次操作。
*/
void creat_heap(int* arr,size_t root,size_t len)
{
	if(root >= len) return;
	int left = root*2+1,right = root*2+2;

	creat_heap(arr,left,len);
	creat_heap(arr,right,len);

	int max = root;
	if(left < len)
	{
		if(arr[left] > arr[max])
			max = left;
	}

	if(right < len)
	{
		if(arr[right] > arr[max])
			max = right;
	}
	
	if(max != root)
		swap(arr[max],arr[root]);
}

void heap_sort(int* arr,size_t len)
{
	for(int i=0; i<len; i++)
	{
		creat_heap(arr,0,len-i);
		swap(arr[0],arr[len-i-1]);
	}
}

int main()
{
	int arr[10];

	for(int i=0; i<10; i++)
	{
		arr[i] = rand() % 100;
	}
	show_arr(arr,10);			//显示初始数组
	heap_sort(arr,1000);		//进行堆排序
	show_arr(arr,10);			//显示排序后的数组

}

